\section{Appendix~\ref{app:s:3fac}: Details Missing from the Proof of Theorem~\ref{thm:3facilities}}
\label{app:s:3fac}

\subsection{Proof of Theorem~\ref{thm:3facilities}: Case where $F_3(\vec{x}) = x_3$}
\label{app:s:3facilities}

Next, we consider the case where $F_3(\vec{x}) = x_3$, which is symmetric to the case where $F_3(\vec{x}) = x_4$. As before, both $x_3$ and $x_4$ are served by the facility at $x_3$, and there is a $x_4$-hole $(l, r)$ in the image set $I_4(\vec{x}_{-4})$.
%
We note that $3\lambda^2+\lambda = x_3 \leq l < x_4 = 3\lambda^2+\lambda+1$, since $x_3 \in F(\vec{x})$ and $x_4 \not\in F(\vec{x})$, and that $r \leq 5\lambda^2+\lambda+2$.
%
As for the latter, if $r > 5\lambda^2+\lambda+2$, then $y = 4\lambda^2+\lambda+1$ would lie in the left half of the hole $(l, r)$. Therefore, if agent $4$ moves to $y$, by $F$'s strategyproofness, the nearest facility to $y$ in $F(\vec{x}_{-4}, y)$ would be at $l < 3\lambda^2+\lambda+1$, and thus $\cost[F(\vec{x}_{-4}, y)] > \lambda^2$. Since the optimal cost for instance $(\vec{x}_{-4}, y)$ is $\lambda$, the approximation ratio of $F$ would be $\lambda > \rho$.

Let us now consider the instance $\vec{x}' = (\vec{x}_{-4}, r-\eps)$, where $\eps \in (0, 1]$ is chosen small enough that $r-\eps$ lies in the right half of the hole $(l, r)$ and the instance $(0, \lambda, r-\eps, r)$ is $(1|2|3,4)$-well-separated. Since $F$ is strategyproof, and since $r$ is the nearest point in $I_4(\vec{x}_{-4})$ to $r-\eps$, $r \in F(\vec{x}')$.
%
Then, we consider the instance $\vec{x}'' = (\vec{x}'_{-3}, r)$ (as before, since we require that the agents are arranged on the line in increasing order of their indices, the agents $3$ and $4$ switch indices in $\vec{x}'$ and $\vec{x}''$).
%
Since $F$ is anonymous and strategyproof, and since $r \in F(\vec{x}')$, $x''_4 = r \in F(\vec{x}'')$. Moreover, by Proposition~\ref{prop:right_cover}, $x''_3 = r-\eps \in F(\vec{x}'')$, because for the $(1|2|3,4)$-well-separated instance $\vec{x}$, $F_3(\vec{x}) = x_3$, and $\vec{x}''$ is an $(1|2|3,4)$-well-separated instance with $x''_3 \geq x_3$.
%
Since both $x''_3, x''_4 \in F(\vec{x}'')$, either the agents $1$ and $2$ are served by the same facility of $F(\vec{x}'')$ or the agent $2$ is served by the facility at $r-\eps$. In both cases, $\cost[F(\vec{x}'')] \geq \lambda$. On the other hand, the optimal cost for $\vec{x}''$ is $\eps \leq 1$, and the approximation ratio of $F$ is at least $\lambda > \rho$. \qed 